package z;

import java.util.LinkedList;

/**
 * @author fangkun
 * @create 2023-01-09-9:02
 *
 * 滑动窗口内最大值：
 * 假设一个固定大小为W的窗口，依次划过arr返回每一次滑出状况的最大值例
 * 如，arr =[4,3,5,4,3,3,6,7],W = 3返回:[5,5,5,4,6,7]
 */
public class SlidingWindowMaxArray {

    public static int[] getMaxWindow(int[] arr, int w){
        //1.判断参数：数组不能为空，w不能小于1，数组长度不能小于w
        if (arr == null || w < 1 || arr.length < w){
            return null;
        }

        //2.单调递减队列，从大到小顺序
        LinkedList<Integer> qmax = new LinkedList<>();

        //3.结果数组
        int[] res = new int[arr.length - w + 1];
        int index = 0;

        //当前位置进入窗口
        for (int i = 0; i < arr.length; i++) {
            while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]){
                qmax.pollLast();
            }

            qmax.addLast(i);

            if (qmax.peekFirst() == i - w){
                qmax.pollFirst();
            }

            if (i >= w - 1){
                res[index++] = arr[qmax.peekFirst()];
            }
        }

        return res;
    }

    public static void main(String[] args) {
        int[] maxWindow = getMaxWindow(new int[]{4, 3, 5, 4, 3, 3, 6, 7}, 3);
        for (int i = 0; i < maxWindow.length; i++) {
            System.out.print(maxWindow[i] + ",");
        }
    }
}
